from random import randint

from utils.log import Log
from utils.generator import Generator
from utils.list_node import Node


# 欧洲集体右转,都要开始优先考虑本国利益了,老美接下来该何去何从

class ListGenerator(Log):
    def __init__(self, length=randint(10, 20)):
        super(ListGenerator, self).__init__()
        self.length = length

    def do(self, intersect=False):
        if intersect:
            intersect_index = randint(0, self.length - 1)
        intersect_node = None
        header = Node(Generator().single_val())
        self.info(f"header {header}")
        if intersect and (intersect_index == 0):
            intersect_node = header
        prev = header
        for i in range(1, self.length):
            n = Node(Generator().single_val())
            self.info(f"{n}")
            prev.next = n
            prev = n
            if intersect and (intersect_index == i):
                intersect_node = n
        if intersect:
            self.info(f"intersect node {intersect_node}")
            prev.next = intersect_node
        return header


class FirstIntersectNode(Log):
    # ref: https://www.bilibili.com/video/BV1A14y1i7GY/?spm_id_from=333.788.recommend_more_video.10&vd_source=ad559e41b561d48861f70d0187e51e02
    # 56:09
    def __init__(self, header):
        super(FirstIntersectNode, self).__init__()
        self.header = header

    def get(self):
        if self.header is None or self.header.next is None or \
                self.header.next.next is None:
            return None

        fast = self.header.next.next
        slow = self.header.next
        while fast.next and fast.next.next and (fast != slow):
            fast = fast.next.next
            slow = slow.next

        if fast == slow:
            fast = self.header
            while fast != slow:
                fast = fast.next
                slow = slow.next
            return fast


if __name__ == '__main__':
    fin = FirstIntersectNode(ListGenerator().do(intersect=True))
    print(fin.get())
